#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> row = {1, -1, 0, 0};
vector<int> col = {0, 0, 1, -1};

//733.图像渲染
int cur;
void dfs1(vector<vector<int>>& image,int i,int j,int color){
    //刚开始时先修改当前位置的颜色，再四个方向移动
    image[i][j] = color;

    for (int k = 0; k < 4;k++){
        int x = i + row[k], y = j + col[k];
        if(x>=0&&x<image.size()&&y>=0&&y<image[i].size()&&image[x][y]==cur){
            dfs1(image, x, y, color);
        }
    }
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color){
    //特殊情况，如果要修改的颜色等于当前的颜色，直接返回
    if(image[sr][sc]==color){
        return image;
    }

    cur = image[sr][sc];

    dfs1(image, sr, sc, color);
    return image;
}

//200.岛屿数量
vector<vector<bool>> check;
int ret1 = 0;
void dfs2(vector<vector<char>>& grid,int i,int j){
    for (int k = 0;k<4;k++){
        int x = i + row[k], y = j + col[k];
        if (x >= 0 && x < grid.size() && y >= 0 && y < grid[i].size() && grid[x][y] == '1' && check[x][y] == false)
        {
            check[x][y] = true;
            dfs2(grid, x, y);
        }
    }
}
int numIslands(vector<vector<char>> &grid){
    //先初始化二维布尔数组
    check.resize(grid.size());
    for (int i = 0; i < check.size();i++){
        check[i].resize(grid[i].size());
    }

    //遍历原始数组先找到目标岛屿也就是1，然后对当前位置进行深度搜索
    for(int i=0;i<grid.size();i++){
        for (int j = 0; j < grid[i].size();j++){
            if(grid[i][j]=='1'&&check[i][j]==false){
                dfs2(grid, i, j);
                ret1++;
            }
        }
    }

    return ret1;
}


//695.岛屿的最大面积
int ret2 = 0;
//这里设置一个每次深度搜索的面积变量，如果设置成参数由于函数的特性会自动回溯，在每次深度搜索的过程中不能回溯
//要本次深度搜索全部结束后再回溯
int path = 0;
void dfs3(vector<vector<int>>&grid,int i,int j){
    //每次递归调用时，面积加一
    path++;
    ret2 = max(ret2, path);

    for (int k = 0;k<4;k++){
        int x = i + row[k], y = j + col[k];
        if (x >= 0 && x < grid.size() && y >= 0 && y < grid[i].size() && grid[x][y] == 1 && check[x][y] == false)
        {
            check[x][y] = true;
            dfs3(grid, x, y);
        }
    }

}
int maxAreaOfIsland(vector<vector<int>>& grid){
    //先初始化二维布尔数组
    check.resize(grid.size());
    for (int i = 0; i < check.size();i++){
        check[i].resize(grid[i].size());
    }

    //遍历原始数组先找到目标岛屿也就是1，然后对当前位置进行深度搜索
    for(int i=0;i<grid.size();i++){
        for (int j = 0; j < grid[i].size();j++){
            if(grid[i][j]==1&&check[i][j]==false){
                check[i][j] = true;
                dfs3(grid, i, j);
                //回溯
                path = 0;
            }
        }
    }

    return ret2;
}


//130.被围绕的区域
int m = 0;
int n = 0;
void dfs4(vector<vector<char>>& board,int i,int j){
    board[i][j] = '.';

    for (int k = 0; k < 4;k++){
        int x = i + row[k], y = j + col[k];
        if(x>=0&&x<=m&&y>=0&&y<=n&&board[x][y]=='O'){
            dfs4(board, x, y);
        }
    }
}
void solve(vector<vector<char>>& board){
    m = board.size() - 1;
    n = board[0].size() - 1;
    //正难则反
    //先将边界上的‘o'通过dfs将连通块修改成'.'表示边界上的不能修改
    for (int j = 0; j <= n;j++){
        if(board[0][j]=='O'){
            dfs4(board, 0, j);
        }
        if(board[m][j]=='O'){
            dfs4(board, m, j);
        }
    }
    for (int i = 0; i <= m; i++){
        if(board[i][0]=='O'){
            dfs4(board, i, 0);
        }
        if(board[i][n]=='O'){
            dfs4(board, i, n);
        }
    }

    //遍历原始数组，遇到'o'表示除边界连通块以外需要修改的，遇到'.'表示边界的连通块，修改回'o'
    for (int i = 0; i <= m;i++){
        for (int j = 0; j <= n;j++){
            if(board[i][j]=='.'){
                board[i][j] = 'O';
            }
            else if(board[i][j]=='O'){
                board[i][j] = 'X';
            }
            else{
                continue;
            }
        }
    }
}


//417.太平洋大西洋水流问题
void dfs5(vector<vector<int>>& heights,int i,int j,vector<vector<bool>>& check){
    check[i][j] = true;

    for (int k = 0; k < 4; k++){
        int x = i + row[k], y = j + col[k];
        //对当前位置深度搜索，将四个方向比当前位置高的标记为true
        if(x>=0&&x<heights.size()&&y>=0&&y<heights[x].size()&&check[x][y]==false&&heights[x][y]>=heights[i][j]){
            dfs5(heights, x, y, check);
        }
    }
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights){
    int n=heights.size();
    int m = heights[0].size();
    //正难则反，不直接找二维数组中的峰值位置既可以流向太平洋也可以流向大西洋，而是从两个向数组内部倒着流，找到峰值
    //设置两个二维数组用来标记太平洋和大西洋可以流向的位置
    vector<vector<bool>> pac(n, vector<bool>(m));
    vector<vector<bool>> alt(n, vector<bool>(m));

    //先处理太平洋，上左两个边界
    for (int j = 0; j < m; j++){
        dfs5(heights, 0, j, pac);
    }
    for (int i = 0; i < n; i++){
        dfs5(heights, i, 0, pac);
    }

    //再处理大西洋，下右两个边界
    for (int j = 0; j < m; j++){
        dfs5(heights, n - 1, j, alt);
    }
    for (int i = 0; i < n; i++){
        dfs5(heights, i, m - 1, alt);
    }

    //遍历两个二维布尔数组，找到同时为true的位置，返回
    vector<vector<int>> ret;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if(pac[i][j]==true&&alt[i][j]==true){
                ret.push_back({i,j});
            }
        }
    }

    return ret;
}


//529.扫雷游戏
vector<int> dx = {1, -1, 0, 0, -1, -1, 1, 1};
vector<int> dy = {0, 0, 1, -1, 1, -1, 1, -1};
void dfs6(vector<vector<char>>& board,int i,int j){
    //先遍历当前位置的八个方向，统计地雷的个数
    int count = 0;
    for (int k = 0; k < 8; k++){
        int x = i + dx[k], y = j + dy[k];
        if(x>=0&&x<board.size()&&y>=0&&y<board[x].size()&&board[x][y]=='M'){
            count++;
        }
    }

    //如果地雷个数不为零，修改当前位置的标记为地雷个数然后返回
    if(count){
        board[i][j] = count + '0';
        return;
    }
    //如果地雷个数为零，先修改当前位置为空格，再分别递归八个方向
    else{
        board[i][j] = 'B';
        for (int k = 0; k < 8; k++){
            int x = i + dx[k], y = j + dy[k];
            //如果相邻方向是为遍历，就递归
            if(x>=0&&x<board.size()&&y>=0&&y<board[x].size()&&board[x][y]=='E'){
                dfs6(board, x, y);
            }
        }
    }
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click){
    //如果刚开始就是地雷，直接修改并返回
    if(board[click[0]][click[1]]=='M'){
        board[click[0]][click[1]] = 'X';
        return board;
    }

    dfs6(board, click[0], click[1]);

    return board;
}


//LCR.130.衣橱整理
//最傻逼的题
int ans = 0;
void dfs7(int m,int n,int cnt,int i,int j){
    //现将当前位置标记已走过,个数加一
    ans++;
    check[i][j] = true;
    for (int k = 0; k < 4; k++){
        int x = i + dx[k], y = j + dy[k];
        if(x>=0&&x<m&&y>=0&&y<n&&check[x][y]==false){
            //判断位数之和
            int sum = 0;
            while(x){
                sum +=x % 10;
                x /= 10;
            }
            while(y){
                sum += y % 10;
                y /= 10;
            }
            //上面的两个循环修改了x,y的值，这里要从新赋值
            x = i + dx[k], y = j + dy[k];
            if(sum<=cnt){
                dfs7(m, n, cnt, x, y);
            }
        }
    }
}
int wardrobeFinishing(int m, int n, int cnt){
    //如果cnt为0，直接返回
    if(cnt==0){
        return 1;
    }
    //初始化二维布尔数组
    check.resize(m);
    for (int i = 0; i < m; i++){
        check[i].resize(n);
    }
    //深度搜索
    dfs7(m, n, cnt, 0, 0);
    return ans;
}


int main(){
    wardrobeFinishing(4, 7, 5);
    return 0;
}